package sort.insert;

import sort.common.PrintArr;
import sort.common.SortClass;

/**
 * 希尔排序
 * 插入排序的基础上，外面套一层gap递增量的循环；可以理解为插入排序的分组化
 * 分组间隔量依次从arr.length/2递减到1
 */
public class ShellSort extends PrintArr implements SortClass {


    @Override
    public void sort(int[] arr) {
        for (int gap = arr.length/2;gap>0; gap /= 2){
            //内部为插入排序，地增量由1改为gap
            for (int i = gap; i < arr.length; i++) {
                int num = arr[i], j = i -gap;
                while (j>=0 && arr[j]> num){
                    arr[j+gap] = arr[j];
                    j -= gap;
                }

                //注意这里原来是j+1，因为j多减了一次
                arr[ j+gap ] = num;
            }
        }
    }

    public static void main(String[] args) {
        ShellSort shellSort = new ShellSort();
        int[] arr = {4, 2, 1, 5, 7, 11, 32, 43, 22, 15};
        shellSort.sort(arr);
        shellSort.printArr(arr);
    }
}
